UVA1218 Perfect Service

一道很不错的树形dp。

dp[u][f]dp[u][f] 为以uu为根的子树。

f=0f=0,表示uu为服务器,那么uu的儿子和父亲既可以是服务器,也可以不是。

f=1f=1,表示uu的父亲为服务器,那么uu的儿子一定不为服务器。

f=2f=2,表示uuuu的父亲均不为服务器,那么uu的儿子中一定有一个是服务器。

那么转移式为:

dp[u][0]=vsonumin(dp[v][0],dp[v][1])dp[u][0]=\sum_{v \in son_u}min(dp[v][0],dp[v][1])

dp[u][1]=vsonudp[v][2]dp[u][1]=\sum_{v \in son_u}dp[v][2]

dp[u][2]=min(dp[v1][2]+dp[v2][2]+...+dp[vk][0]+...+dp[vs][2])dp[u][2]=min(dp[v_1][2]+dp[v_2][2]+...+dp[v_k][0]+...+dp[v_s][2])

其中 ssuu 的子结点个数 , kk 是枚举的为服务器的那个子节点。

这样转移需要Θ(n)\Theta(n) , 经过观察发现,求和的部分与 dp[u][1]dp[u][1] 除了枚举的 dp[vk][0]dp[v_k][0] 是一致的 , 于是就可以化简为:

dp[u][2]=min(dp[u][2],dp[u][1]dp[v][2]+dp[v][0])dp[u][2]=min(dp[ u ][ 2 ] , dp[ u ][ 1 ] - dp[ v ][ 2 ] + dp[ v ][ 0 ])

最后注意dp\text{dp}的极大值,用 infinf 可能会爆 intint , 开成 n+5n+5 即可。

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;

const int MAXN = 10000;
int n , u , v , dp[ MAXN + 5 ][ 3 ];


vector< int > Graph[ MAXN + 5 ];

void dfs( int u , int fa ) {
    dp[ u ][ 0 ] = 1; dp[ u ][ 1 ] = 0;
    for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
        int v = Graph[ u ][ i ];
        if( v == fa ) continue;
        dfs( v , u );

        dp[ u ][ 0 ] += min( dp[ v ][ 0 ] , dp[ v ][ 1 ] );
        dp[ u ][ 1 ] += dp[ v ][ 2 ];
        dp[ u ][ 2 ] = min( dp[ u ][ 2 ] , dp[ u ][ 1 ] - dp[ v ][ 2 ] + dp[ v ][ 0 ] ); 
    }
}

int main( ) {
    while( scanf("%d",&n) ) {
        for( int i = 1 ; i <= n ; i ++ ) {
            Graph[ i ].clear( );
            dp[ i ][ 0 ] = dp[ i ][ 1 ] = dp[ i ][ 2 ] = MAXN;
        }

        for( int i = 1 ; i <= n - 1 ; i ++ ) {
            scanf("%d %d",&u,&v);
            Graph[ u ].push_back( v );
            Graph[ v ].push_back( u );
        }
        
        dfs( 1 , 0 );
        printf("%d\n", min( dp[ 1 ][ 0 ] , dp[ 1 ][ 2 ] ) );

        scanf("%d",&n);
        if( n == -1 ) break;
    }
    return 0;
}